home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / ABUSESRC.ZIP / AbuseSrc / imlib / linked.c < prev    next >
C/C++ Source or Header  |  1996-04-11  |  4KB  |  156 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #include "linked.hpp"
  6.  
  7. // unlink take a node out of the linked list, but does not dispose of the memory
  8. int linked_list::unlink(linked_node *p)
  9. {
  10.   linked_node *q;
  11.   if (first())        // if there are any nodes..
  12.   {
  13.     if (first()==p)  // if they want to unlinkt the first node
  14.     {
  15.       fn->last()->set_next(fn->next());   // set the first's last's next to the first's next
  16.       fn->next()->set_last(fn->last());    // set the first next's last to the first last
  17.       if (fn->next()==fn)                   // if there is ony one node
  18.       { fn=NULL; cn=NULL; }                   // clear the list
  19.       else fn=p->next();                  // else point the first pointer to the next node
  20.       nn--;                              // decrement the number of nodes in the list
  21.       return 1;
  22.     }
  23.     else
  24.     {
  25.       q=first()->next();
  26.       while (q!=p && q!=first())    // find the node in the list
  27.     q=q->next();
  28.       if (q!=first())                  // is it in the list at all?
  29.       {  q->last()->set_next(q->next());   // yes unlink the pointers
  30.      q->next()->set_last(q->last());
  31.      nn--;
  32.       return 1;
  33.       }                                    // decrement the number of nodes
  34.     }
  35.   }
  36.   return 0;
  37. }
  38.  
  39.  
  40. // this function clears all the nodes in a linked list and dispose of the
  41. // memory for each one by calling is't destructor
  42. linked_list::~linked_list()
  43. {
  44.   if (fn)
  45.     fn->last()->set_next(NULL);  // set the last nodes next to NULL
  46.                                  // so we can go until we hit NULL
  47.   while (fn != NULL)          // repeat until we get to that node
  48.   {
  49.     cn=fn->next();
  50.     delete fn;                // delete the old node
  51.     fn=cn;
  52.   }
  53.   cn=NULL;                   // clear the list
  54.   nn=0;                     // set the number of nodes to 0
  55. }
  56.  
  57. // this function returns the node number a node is in a linked list
  58. // it start at the node and goes backwards until it reaches the first
  59. // node
  60. int linked_list::node_number(linked_node *p)
  61. {
  62.   int x;
  63.   x=1;
  64.   while (p!=first())
  65.   { x++; p=p->last(); }
  66.   return x;
  67. }
  68.  
  69.  
  70. // this function returns a pointer to the xth node
  71. class linked_node *linked_list::get_node(int x)
  72. {
  73.   class linked_node *p;
  74.   p=fn;             // start tat the first node
  75.   while (x--!=1) p=p->next();  // go forward X-1 nodes
  76.   return p;
  77. }
  78.  
  79.  
  80. // this function adds a node to the end of a linked_list
  81. void linked_list::add_end(class linked_node *p)
  82. {
  83.   nn++;
  84.   if (fn==NULL)        // if there are no nodes, then this one becomes the first
  85.   { fn=p;
  86.     fn->set_next(fn);  // and it poits to itself for first and last
  87.     fn->set_last(fn);
  88.   }
  89.   else
  90.   {
  91.     p->set_last(fn->last());  // otherwise add it in at the end
  92.     p->set_next(fn);
  93.     fn->last()->set_next(p);
  94.     fn->set_last(p);          // the first's last pointer points to the node we just added
  95.   }
  96. }
  97.  
  98.  
  99. // to add a node at the fron of the list, just add it at the end and set
  100. // the first pointer to it
  101. void linked_list::add_front(class linked_node *p)
  102. {
  103.   add_end(p);
  104.   fn=p;
  105. }
  106.  
  107.  
  108. // insert adds a node in the list according to is sort value
  109. void linked_list::insert(class linked_node *p)
  110. {
  111.   class linked_node *q;
  112.  
  113.   // if there are nodes, or it belongs at the beginin call add front
  114.   if ((fn==NULL) || (p->compare(fn,sortby)>0))
  115.     add_front(p);
  116.   // else if it goes at the ned call add_end
  117.   else if (p->compare(fn->last(),sortby)<=0)
  118.     add_end(p);
  119.   else      // otherwise we have to find the right spot for it.
  120.   {
  121.     nn++;
  122.     q=fn;
  123.     while (q!=fn->last())  // q starts at the front
  124.     { q=q->next();
  125.       if (p->compare(q,sortby)>0)  // repeat until we find a value greater than the one we are inserting
  126.       { p->set_next(q);
  127.     p->set_last(q->last());     // insert it with pointers here
  128.     q->last()->set_next(p);
  129.     q->set_last(p);
  130.     q=fn->last();         // set q to the last node so we exit the loop
  131.       }
  132.     }
  133.   }
  134. }
  135.  
  136. linked_list::linked_list(linked_node *first)
  137. { linked_node *prev;
  138.   fn=first; cn=first; sortby=1; nn=0;
  139.   if (first)
  140.   { cn=first;
  141.     do
  142.     {
  143.       nn++;
  144.       prev=cn;
  145.       cn=cn->next();
  146.     } while (cn && cn!=first);
  147.     if (cn==NULL)
  148.     {
  149.       fn->set_last(prev);
  150.       prev->set_next(fn);
  151.     }
  152.     cn=first;
  153.  
  154.   }
  155. }
  156.